package arithmetic2;

/**
 * Created by AJie on 2019/9/5
 * Function :
 * 搜索旋转排序数组 中的 target
 *  结题：
 *  https://leetcode-cn.com/problems/search-in-rotated-sorted-array/solution/er-fen-fa-python-dai-ma-java-dai-ma-by-liweiwei141/
 * 二分模板 TODO https://leetcode-cn.com/problems/search-insert-position/solution/te-bie-hao-yong-de-er-fen-cha-fa-fa-mo-ban-python-/
 *
 *
 */
public class T_035_SearchInFotatedSortedArrayTarget {

    public static void main(String[] args) {
        System.out.println( search(new int []{1,3},1));
    }

    /**
     *
     * 题目给出的是“旋转排序数组”，是“部分有序数组”，我们同样可以一次排除一半或者一半以上元素的方法，即二分查找法。
     * <P>
     * 二分查找法的本质是排除法，是“减而治之”的算法思想的体现，而“二分”只是手段，二分保证了“熵”最大，即在没有任何有效信息的时候，平分是最好的方案。
     * 思路清楚了以后，我们就得确定“有序数组”存在在“原始数组”的哪个子区间里，下面提供了两个比较标准：
     * <P>>
     * 1、中间元素和左边界比较，可以确定出一个区间有序，另一个区间无序；
     *
     * 2、中间元素和右边界比较，也可以确定出一个区间有序，另一个区间无序。
     *
     * 根据 target 落在有序区间或者无序区间进行分类讨论，每一次讨论可以缩小将近一半的搜索区间。
     * 这是解这道题的关键。根据这两个比较标准就能写出两版不同的代码。
     *
     * 作者：liweiwei1419
     * 链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array/solution/er-fen-fa-python-dai-ma-java-dai-ma-by-liweiwei141/
     *
     */
    public static int search(int[] nums, int target) {
        // 中间元素和右边界比较，使用右中位数

        if (nums==null || nums.length<1)return -1;

        int left = 0;
        int right = nums.length-1;// 注意：这里是等于
        while (left < right){// 注意：这里是小于
            int mid = (left + right)>>>1;
            System.out.println("mid --- >"+mid + " L: "+left +"  R: " +right);
            if (nums[mid] > nums[right]){
                // 前有序，包括中间数
                // 6 7 8 9 1 2
                if (nums[left]<= target && target<= nums[mid]){
                    right = mid;
                }else {
                    left = mid + 1;
                }
            }else {
                // 注意：写这个 if 语句的时候，要让分支和上面一样
                // 后有序，包括中间数
                if (target> nums[mid] && target<= nums[right]){
                    left = mid +1 ;
                }else {
                    right = mid ;
                }

//                // TODO: 2019/9/6 mid --- >0 L: 0  R: 1 死循环
//                if (target>= nums[mid] && target<= nums[right]){
//                    left = mid ;
//                }else {
//                    right = mid -1;
//                }
            }
        }
        if (nums[left] == target){
            return left;
        }
        return -1;
    }

    // 中间元素和左边界比较，，使用右中位数
    public static int search2(int[] nums, int target) {
        int len  = nums.length;
        if(len == 0 ){
            return -1;
        }
        int left =0,right = len-1;

        // 注意：这里是等于
        while (left < right){
            int mid = (left + right)>>>1;

            if (nums[mid] > nums[left]){
                //前有序，包括中间数
                if (nums[left]<=target && target < nums[mid]){
                    right = mid -1;
                }else {
                    left = mid;
                }

            }else {
                // 注意：写这个 if 语句的时候，要让分支和上面一样
                // 后有序，包括中间数
                // 8 9 1 2 6 7
                if (nums[mid]<=target && target <= nums[right]){
                    left = mid;
                }else {
                    right = mid -1;
                }
            }
        }

        if (nums[left] == target){
            return left;
        }

        return -1;
    }


}

